import { useMemo, useState } from 'react';
import { TreeNode, buildBSTFromArray, validateBST, searchBST } from '@ds/tree';
import { Space, Input, Typography, Tag, Card, Alert, Empty } from 'antd';
import { useLocation } from 'react-router-dom';

// 验证过程追踪：记录每个节点在递归中的上下界与是否通过
function validateBSTWithTrace(root: TreeNode | null): Array<{
  nodeVal: number;
  lower: number | null;
  upper: number | null;
  pass: boolean;
  reason?: string;
}> {
  const steps: Array<{
    nodeVal: number;
    lower: number | null;
    upper: number | null;
    pass: boolean;
    reason?: string;
  }> = [];
  const dfs = (node: TreeNode | null, lower: number | null, upper: number | null) => {
    if (!node) return;
    let pass = true;
    let reason: string | undefined;
    if (lower !== null && node.val <= lower) {
      pass = false;
      reason = `值 ${node.val} ≤ 下界 ${lower}`;
    }
    if (upper !== null && node.val >= upper) {
      pass = false;
      reason = `值 ${node.val} ≥ 上界 ${upper}`;
    }
    steps.push({ nodeVal: node.val, lower, upper, pass, reason });
    dfs(node.left, lower, node.val);
    dfs(node.right, node.val, upper);
  };
  dfs(root, null, null);
  return steps;
}

function levelOrder(root: TreeNode | null): (number | null)[][] {
  const result: (number | null)[][] = [];
  if (!root) return result;
  const queue: (TreeNode | null)[] = [root];
  while (queue.length) {
    const size = queue.length;
    const level: (number | null)[] = [];
    for (let i = 0; i < size; i++) {
      const node = queue.shift() ?? null;
      if (node) {
        level.push(node.val);
        queue.push(node.left);
        queue.push(node.right);
      } else {
        level.push(null);
      }
    }
    // 避免尾部全是null的层级
    if (level.some((v) => v !== null)) {
      result.push(level);
    }
  }
  return result;
}

export default function BSTVisualizer() {
  const [input, setInput] = useState('5,3,7,2,4,6,8');
  const [searchValue, setSearchValue] = useState('6');
  const location = useLocation();
  const isSearchMode = location.pathname.startsWith('/bst/search');
  const isOverviewMode = location.pathname === '/bst' || location.pathname === '/';
  const isValidateMode = location.pathname.startsWith('/bst/validate');

  const values = useMemo(
    () =>
      input
        .split(/[\,\s]+/)
        .filter(Boolean)
        .map(Number)
        .filter((n) => Number.isFinite(n)),
    [input]
  );
  const root = useMemo(() => buildBSTFromArray(values), [values]);
  const valid = useMemo(() => validateBST(root), [root]);
  const searchNum = useMemo(() => Number(searchValue), [searchValue]);
  const isSearchValid = useMemo(() => Number.isFinite(searchNum), [searchNum]);
  const foundNode = useMemo(
    () => (isSearchValid ? searchBST(root, searchNum) : null),
    [root, searchNum, isSearchValid]
  );
  const levels = useMemo(() => levelOrder(root), [root]);
  const trace = useMemo(() => validateBSTWithTrace(root), [root]);
  const firstInvalid = useMemo(() => trace.find((s) => !s.pass), [trace]);

  return (
    <Space direction="vertical" size="middle" style={{ width: '100%' }}>
      <Typography.Title level={2}>二叉搜索树可视化</Typography.Title>
      {isOverviewMode && (
        <Alert
          message="二叉搜索树概述：定义与验证"
          description={
            <Typography.Paragraph style={{ marginBottom: 0 }}>
              定义：对任意节点，
              <Typography.Text strong>左子树所有节点的值均小于该节点值</Typography.Text>，
              <Typography.Text strong>右子树所有节点的值均大于该节点值</Typography.Text>
              ；本实现中相等值进入右子树。
              <br />
              验证：使用上下界（最小/最大）约束递归检查每个节点是否在有效范围内；若所有节点满足约束则为有效
              BST。
            </Typography.Paragraph>
          }
          type="info"
          showIcon
        />
      )}
      {isValidateMode && (
        <Alert
          message="验证过程（上下界约束）"
          description={
            <Typography.Paragraph style={{ marginBottom: 0 }}>
              自根节点开始，递归传递约束：左子树上界为父节点值，右子树下界为父节点值。每一步检查当前节点是否满足{' '}
              <Typography.Text code>lower &lt; node &lt; upper</Typography.Text>。
              若某一步失败，则可将该节点视为违反 BST 定义的证据。
            </Typography.Paragraph>
          }
          type={firstInvalid ? 'warning' : 'success'}
          showIcon
        />
      )}
      {isSearchMode && (
        <Alert
          message="LeetCode 700. 二叉搜索树中的搜索"
          description={
            <Typography.Paragraph style={{ marginBottom: 0 }}>
              给定二叉搜索树的根节点和一个目标值，返回值等于目标值的节点所对应的子树根节点；若不存在返回
              null。
              <Typography.Link
                href="https://leetcode.cn/problems/search-in-a-binary-search-tree/"
                target="_blank"
                style={{ marginLeft: 8 }}
              >
                题目链接
              </Typography.Link>
            </Typography.Paragraph>
          }
          type="info"
          showIcon
        />
      )}

      <Space>
        <Input
          allowClear
          value={input}
          onChange={(e) => setInput(e.target.value)}
          placeholder="例如: 5,3,7,2,4,6,8"
          style={{ width: 320 }}
        />
        {isSearchMode && (
          <Input
            allowClear
            value={searchValue}
            onChange={(e) => setSearchValue(e.target.value)}
            placeholder="搜索值，例如: 6"
            style={{ width: 160 }}
          />
        )}
      </Space>

      <Space wrap>
        <Alert
          message={`是否有效BST：${String(valid)}`}
          type={valid ? 'success' : 'error'}
          showIcon
        />
        {isSearchMode && (
          <Alert
            message={
              !isSearchValid
                ? '请输入有效数字'
                : foundNode
                  ? `找到节点值：${foundNode.val}`
                  : '未找到'
            }
            type={!isSearchValid ? 'warning' : foundNode ? 'success' : 'info'}
            showIcon
          />
        )}
      </Space>

      {isValidateMode && (
        <Card title="验证步骤（上下界）" size="small">
          {trace.length === 0 ? (
            <Empty description="空树无需验证" />
          ) : (
            <div style={{ display: 'grid', rowGap: 8 }}>
              {trace.map((s, i) => {
                const lowerText = s.lower === null ? '-∞' : String(s.lower);
                const upperText = s.upper === null ? '+∞' : String(s.upper);
                return (
                  <div key={i} style={{ display: 'flex', alignItems: 'center', gap: 8 }}>
                    <Tag color={s.pass ? 'green' : 'red'}>{s.pass ? '✓' : '✗'}</Tag>
                    <Typography.Text>
                      第 {i + 1} 步：节点值 <Typography.Text code>{s.nodeVal}</Typography.Text>
                      ，范围 (<Typography.Text code>{lowerText}</Typography.Text>,{' '}
                      <Typography.Text code>{upperText}</Typography.Text>)
                    </Typography.Text>
                    {!s.pass && s.reason && (
                      <Tag color="red" style={{ marginLeft: 8 }}>
                        {s.reason}
                      </Tag>
                    )}
                  </div>
                );
              })}
            </div>
          )}
        </Card>
      )}

      <Card>
        {levels.length === 0 ? (
          <em>空树</em>
        ) : (
          <div style={{ display: 'grid', gap: 8 }}>
            {levels.map((level, idx) => (
              <div key={idx} style={{ display: 'flex', justifyContent: 'center', gap: 6 }}>
                {level.map((val, i) => (
                  <div
                    key={i}
                    style={{
                      minWidth: 36,
                      minHeight: 36,
                      border: '1px solid #aaa',
                      borderRadius: 18,
                      display: 'flex',
                      alignItems: 'center',
                      justifyContent: 'center',
                      background:
                        val !== null && foundNode && foundNode.val === val ? '#ffe58f' : '#fff',
                    }}
                  >
                    {val === null ? '' : val}
                  </div>
                ))}
              </div>
            ))}
          </div>
        )}
      </Card>

      <Typography.Text type="secondary">
        提示：数组按照当前插入策略构建BST（相等值进入右子树）。
      </Typography.Text>
    </Space>
  );
}
